\section{Introduction}

% Alex: Standard OO "intro" stuff given to programmers, like this Sun's Java tutorial on OOP: http://docs.oracle.com/javase/tutorial/java/concepts/object.html  (or even Alan Kay's hiding of state and messages thoughts: http://userpage.fu-berlin.de/~ram/pub/pub_jf47ht81Ht/doc_kay_oop_en ) talks about objects having "state" that is the values of their "fields" that can "change". Immutability is then disallowing such change - why is that necessary or important and how does it relate to *aliasing*? There is also wikipedia... http://en.wikipedia.org/wiki/Immutable_object :)

Traditional imperative object-oriented (OO) programs consist of objects that have \textit{state} and \textit{behaviour}\footnote{For example: \url{http://docs.oracle.com/javase/tutorial/java/concepts/object.html}.}.
The behaviour is modelled by the methods.
The state is represented by the values of an object's fields --- which can either be primitives or references to other objects.
\textit{Immutable objects} are those whose state does not change after they are initialised~\cite{BirkaE2004,SkoglundW2001,PechtchanskiS2002,TschantzE2005,KnieselT2001,BoylandNR2001,DietlM2005,zibin:2007:immutability,zibin:2010:oigj,oestlund:2008:oui}.

Immutability information is useful in many software engineering tasks, including modeling~\cite{BurdyEtAl05:STTT},
verification~\cite{TkachukD03}, compile- and run-time
optimizations~\cite{Clausen97,PechtchanskiS2002,Salcianu2006}, program
transformations such as refactoring~\cite{Fowler2000}, test input
generation~\cite{ArtziEGKPP2006}, regression oracle
creation~\cite{MarianiP2005,Xie2006}, invariant
detection~\cite{ErnstCGN2001:TSE}, specification
mining~\cite{DallmeierLWZ2006}, and program
comprehension~\cite{DoladoHOH2003}.
%\mde{Add this to the list iff a citation is added:
%for example in the context of concurrency immutable objects are safe to share and cache.}
%Object immutability can be used for pointer analysis and
%optimizations, such as sharing between threads without
%synchronization, and to help prevent hard-to-detect bugs, e.g.,
The importance of immutability is highlighted by the documentation of the \code{Map} interface in Java that states: ``Great care must be exercised if \emph{mutable objects} are used as map keys.  The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map.''

The notion of immutability is not as straightforward as it might seem, and
many different definitions of immutability exist.
%
Immutability may be deep (transitive) or shallow.  In deep
immutability, every object referred to by an immutable object must itself
be immutable; in shallow immutability, the object's fields cannot be
reassigned, but their referents may be mutated.
%
Immutability guarantees may hold for every field of an object, or may
exclude certain fields such as those used for caching.
%
Immutability may be abstract or concrete.  Concrete immutability forbids
any change to an object's in-memory representation; abstract immutability
permits benevolent side effects that do not affect the abstraction, such as
caching values, rebalancing trees, etc.
%
Immutability guarantees may hold immediately or may be delayed.  An
immediate guarantee holds as soon as the constructor completes; a delayed
guarantee permits initialization of a data structure to continue,
effectively modifying an immutable object, which is necessary to allow
circular initialisation for immutable data structures.
%
Immutability guarantees can be about objects or references.  A read-only
reference cannot be used for mutation,
but the underlying object can be mutated by an aliasing reference; an
immutable object is never changed by any reference to it.
%
This paper discusses these and other issues, and presents language designs
that address them.


%\alex{If the above is what we need for the introduction then I can add some code (trying to be non-language specific) examples for each of the three issues above or otherwise expand on them?}

%\subsection{Old Text}
%
%Traditional imperative object-oriented languages group data and
%behavior into stateful \textit{objects}. An object's state is
%typically represented by the values stored in \textit{mutable}
%fields. 
%%% Mike doesn't see why this is relevant:
%% Commonly, fields either store \textit{primitive} values
%% (e.g. integers, doubles) or \textit{references} to other
%% objects.
%Multiple references to the same object are called
%\textit{aliases}. In this chapter, we explore how to make parts of
%object-oriented programs \textit{immutable}, which problems arise
%when doing so, and proposed solutions to many of these problems.
%
%\mde{This introduction doesn't state what is the purpose of this chapter.
%  Overall, why are immutability and aliasing related?  Why would one even
%  discuss them together in a single book chapter?  The first paragraph of
%  Section~\ref{s:complementing-immutability} hints at the reason, but that
%  is far too late for that information to appear.  There are other
%  reasons as well, such as that ownership can give a hint as to what parts
%  of an object's representation can change without changing its abstract
%  value.  All of this needs a substantial discussion in the introduction.
%}
%
%\mde{This paper is very Java-specific.  I would like to see an explicit
%  discussion of applicability to other object-oriented languages, or at the
%  least a claim (probably untrue, though) that all the concepts and
%  discussions apply immediately to every other OO language.}
%
% \textit{read-only} and \textit{mutable} in the type systems used
% by the functional languages and users are often forced to hide
% mutability.

% just like the
% monads hide the changing state of the external world from the ``pure''
% and immutable functional setting.

%% Yoav didn't like the above monads comparison as "overgeneralisation".

\textit{Outline.}
Section~\ref{s:immutability} introduces the rich concept of immutability and its variations.
Section~\ref{s:immutability-current} outlines the current state of immutability support in object-oriented programming languages.
Section~\ref{s:immutability-future} provides a number of motivations and describes advantages of proposed ways to support immutability mostly on top of a Java-like language.
%Section~\ref{s:complementing-immutability} explains how ownership can help provide immutability support in the presence of aliasing.
% goes beyond
%immutability and discusses a selection of related concepts that might be
%necessary before full immutability support is the
%norm.\mde{This synopsis of Section~\ref{s:complementing-immutability} is
%  vague and does not clarify to readers the point of the section.}
Section~\ref{s:major-proposals} quickly tours through the major
recent proposals for adding immutability while extracting common themes and
highlighting the differences. Section~\ref{s:discussion} discusses the
immutability concept in more general setting, and Section~\ref{s:conclusion}
concludes.

%%% Local Variables: 
%%% TeX-command-default: "PDF"
%%% End: 

%  LocalWords:  OO behaviour modelled
